Content addressable memory (CAM) devices are often used in network switching and routing systems to determine forwarding destinations and permissions for data packets. A CAM device can be instructed to compare a search key obtained from an incoming packet with contents of a forwarding or classification database (referred to collectively herein as a search database) stored in an associative storage array within the CAM device. If the search key matches an entry in the database, the CAM device generates a match address that corresponds to the matching entry, and asserts a match flag to signal the match. The match address is then typically used to address another storage array, either within or separate from the CAM device, to retrieve forwarding information for the packet.
In many cases, the search database is too large to be stored within a single CAM device and is instead distributed within multiple CAM devices that collectively constitute a CAM system. A search operation within the CAM system involves simultaneously searching the search database components in each of the constituent CAM devices and, if matches are detected in more than one CAM device, resolving between the corresponding match addresses according to a prioritizing policy. In some CAM systems, multiple match conditions are resolved by an ASIC (application-specific integrated circuit) or other back-end processing device that receives search results from each of the constituent CAM devices. In other CAM systems, commonly referred to as cascaded CAM systems, multiple match conditions are resolved by the constituent CAM devices themselves.
In a relatively simple class of cascaded CAM systems, each of the constituent CAM devices has a fixed priority relative to the other constituent CAM devices so that multiple match conditions may be resolved based solely on the identities of the match-detecting CAM devices. For example, in a cascade of eight CAM devices having priorities ranging from highest to lowest, a match address generated by the highest priority device will always have a higher priority (and therefore be selected for output) over a match address generated by any of the lower priority CAM devices.
In a more complex class of cascaded CAM systems, the priorities of individual entries in the search database are programmable, for example, to simplify the insertion and deletion of database entries having intermediate priorities. In such programmable-priority CAM systems, each constituent CAM device having a key-matching entry outputs both the match address and a corresponding priority value and wherein resolution of multiple match conditions involves a comparison of priority values output by competing CAM devices to determine a priority winner.
FIG. 1 illustrates a prior-art programmable-priority CAM system 100 having three CAM devices (CAM1, CAM2 and CAM3) coupled in cascade. The CAM devices simultaneously search their respective databases for entries that match an incoming search key (KEY) and generate respective search results that each include a match flag, priority number and match address. The match flag indicates whether a match was detected and therefore whether the corresponding priority number and match address are valid, and the priority number, if valid, indicates the priority of the corresponding match address. The priority numbers produced by the CAM devices ripple both downward and upward through the sequence of CAM devices (i.e., from CAM1 to CAM2 to CAM3, and from CAM3 to CAM 2 to CAM1) in a timed progression (e.g., timed by a system clock signal) and according to the following logic:                Each CAM device waits to receive a logic-low signal at its cascade-down input (CDI), then (1) asserts a logic-low signal at its cascade-down output (CDO) (which is otherwise held high) and (2) compares its self-produced priority number (i.e., local priority number) with a priority number presented at its cascade-down input (PDI) and outputs the priority winner (i.e., the local priority number if both valid and numerically equal to or lower than the priority number at the PDI, and otherwise the priority number at the PDI) at its priority-down output (PDO); and        Each CAM device waits to receive a logic-low signal at its cascade-up input (CUI), then (1) asserts a logic-low signal at its cascade-up output (CUO) (which is otherwise held high) and (2) compares its local priority number with a priority number presented at its cascade-up input (PUI) and outputs the priority winner at its priority-up output (PUO)        Each CAM device outputs its match address onto the output bus upon determining that its local priority number is the priority winner in the comparison with the priority number presented at the PDO and in the comparison with the priority number presented at the PDI.        
CAM1, by virtue of its ground-connected CDI, is the first device to compare its local priority number to the priority number presented at its PDI, and outputs the priority winner to the PDI of CAM2. CAM1 also lowers the signal at the CDI of CAM2, enabling CAM2 to compare its local priority number to the priority winner delivered by CAM1 and, in turn, to output a priority winner to CAM3. CAM3, receives a low signal from CAM2 at its CDI and, in response, compares its local priority number to the priority winner delivered by CAM2 to complete the downward ripple of priority numbers. An upward ripple of priority comparisons is carried out simultaneously with, and in the same manner as, the downward ripple using the CUI, PUI, CUO and PUO pins of each CAM device. By this operation, if a given CAM device has in fact detected a highest priority match (i.e., HPM: a match address for which the corresponding priority number has a higher priority than the priority numbers associated with any other match addresses generated within the CAM system 100), then the CAM device will eventually determine its local priority number to be the winner of comparisons performed in both the upward and downward rippling of priority numbers and, in response, enable the HPM onto output bus 103.
Reflecting on the up/down priority number rippling in CAM system 100, it is evident that the longest-latency HPM determination occurs when the CAM device at either end of the device cascade, CAM1 or CAM3, is the source of the HPM. Stated generally, because N priority number comparisons are performed in sequence to traverse a cascade of N CAM devices, the worst-case HPM latency is proportional to the number of CAM devices in the system. Consequently, the maximum tolerable HPM latency for a given application constrains the number of CAM devices that may be cascaded using the up/down priority number rippling technique of system 100.
FIG. 2 illustrates another prior-art programmable-priority CAM system 150 referred to herein as a master-slave CAM system. In the master-slave CAM system 150, a master CAM device (MASTER), and a set of N slave devices (SLAVE1-SLAVEN) each simultaneously search their respective databases for entries that match an incoming search key (KEY), producing respective match flags, match addresses and priority numbers. The master CAM device receives a match flag and corresponding priority number (MF, P) from each of the slave CAM devices, and compares the slave-supplied priority numbers with one another and with its own local priority number to determine a priority winner (e.g., a lowest numerical priority number for which the corresponding match flag is asserted). If the local priority number is the priority winner, the master CAM device outputs the corresponding match address onto output bus 153 as the HPM. If one of the slave CAM devices sourced the priority winner, the master CAM device outputs an enable signal to the slave device (i.e., one of enable signals, E1-EN) to enable the slave device to output the HPM onto output bus 153.
By centralizing the priority number comparison operation within a single CAM device (i.e., the master CAM device), the per-device latency penalty of the up/down priority number rippling embodiment is avoided, but at the cost of significantly increasing the pin count of the CAM devices (i.e., assuming, as is desirable, that each of the CAM devices can be interchangeably operated as a master or slave) and signal routing complexity. For example, in a master-slave CAM system having a master CAM device and seven slave CAM devices, each of which generates a 12-bit priority number, 84 pins are consumed by the priority number interface alone (additional pins are consumed by the match flag inputs and enable outputs), thus increasing the cost of the CAM devices and therefore the overall system. The increased signal routing complexity may necessitate additional circuit board layers to achieve the required master-slave interconnections without path conflicts, further increasing system cost.